package com.LeetCode.String;

import org.junit.Test;

import java.util.HashSet;

/**
 * 最长重复子串
 */
public class LongestDupSubString {
    int mod = (int) (1e9 + 7);
    //前26个素数
    int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
            31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
            73, 79, 83, 89, 97, 101};


    private long[] hash;
    private long[] power;
    private int[] ansPos;
    private  final long P = 805306457;

    public String longestDupSubstring(String S) {

        int len = S.length();
        hash = new long[len];
        power = new long[len];
        ansPos = new int[2];

        int l = 0, r = S.length();
        while(l<r){
            int L = (l + r) >>> 1;
            String str = Search(S,L);
            if(str.equals("")) r = L - 1;
            else l = L;
        }
        return Search(S,l);
    }

    public void calcHashAndPower(String s){
        hash[0] = s.charAt(0);
        power[0] = 1;
        for(int i = 1; i<s.length(); i++){
            hash[i] = (hash[i-1] * P + s.charAt(i)) % mod;
            power[i] = (power[i-1] * P ) % mod;
        }
    }

    public String Search(String s, int L){
        HashSet<Long> seen = new HashSet<>();
        for(int l = 0; l < s.length() - L + 1;  l++){
            String str = s.substring(l,l + L);
            long hash = getHash(l,l+L);
            if(seen.contains(hash))
                return str;
            else
                seen.add(hash);
        }

        return "";
    }

    public long getHash(int l , int r){
        if(l == 0)
            return hash[r];
        return (hash[r] - power[r - l + 1] * hash[l - 1] % mod + mod) % mod;
    }

    @Test
    public void test(){
        System.out.println(longestDupSubstring("banana"));
//        System.out.println(Search("banana",3));
    }
}
